class Solution:

    # 使用内置 API
    def reverseWords1(self, s: str) -> str:
        return " ".join(reversed(s.split()))

    def reverse_each_word(self, chars: List[str]) -> str:
        n = len(chars)
        slow, fast = 0, 0

        while fast < n:
            while fast < n and chars[fast] != ' ':
                fast += 1
            self.reverse(chars, slow, fast - 1)
            fast += 1
            slow = fast

        return ''.join(chars)


    def reverse(self, chars: List[str], left: int, right: int) -> None:
        while left < right:
            chars[left], chars[right] = chars[right], chars[left]
            left += 1
            right -= 1

    # 删除字符串中所有的空字符，但是单词之间需要一个空字符隔开
    # 时间复杂度：O(n)
    # 空间复杂度：O(1)，原地删除空字符
    def trim(self, s: str) -> str:
        chars = list(s)
        n = len(chars)
        slow, fast = 0, 0

        while fast < n:
            if chars[fast] != ' ' or (fast >= 1 and chars[fast - 1] != ' '):
                chars[slow] = chars[fast]
                slow += 1
            fast += 1

        if slow >= 1 and chars[slow - 1] == ' ':
            slow -= 1

        return ''.join(chars[0:slow])

    # 不使用内置 API
    def reverseWords(self, s: str) -> str:
        s = self.trim(s)
        chars = list(s)
        self.reverse(chars, 0, len(chars) - 1)
        self.reverse_each_word(chars)
        return ''.join(chars)

